class Solution {
public:
bool bfs(vector<vector<int>>& grid,int k)
{
    int n=grid.size();
    queue<int>qe;
    qe.push(0);
    vector<int>visit(n*n+1,0);
    visit[0]=1;
    while(!qe.empty())
    {
        int sum=qe.front();
        int x=sum/n,y=sum%n;
        qe.pop();
        if(x==n-1&&y==n-1) return true;
        vector<pair<int,int>>arr{{-1,0},{1,0},{0,-1},{0,1}};
        for(auto i :arr)
        {
            int a=i.first+x,b=i.second+y;
            if(a<0||a>n-1||b<0||b>n-1) continue;
            int ans=a*n+b;
            if(!visit[ans]&&grid[a][b]<=k)
            {
                visit[ans]=1;
                qe.push(ans);
            }
        }
    }
    return false;
}
    int swimInWater(vector<vector<int>>& grid) {
        int n=grid.size();
        int l=0,r=n*n-1;
        if(bfs(grid,grid[0][0]))
        return grid[0][0];
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(bfs(grid,mid))
            {
                r=mid;
            }
            else
            {
                l=mid+1;
            }
        }
        return l;
    }
};